package com.lw.leetcode.bit.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 6186. 按位或最大的最小子数组长度
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/18 21:45
 */
public class SmallestSubarrays {

    public static void main(String[] args) {
        SmallestSubarrays test = new SmallestSubarrays();

        // [3,3,2,2,1]
//        int[] arr = {1, 0, 2, 1, 3};

        // [2,1]
//        int[] arr = {1, 2};

        // [1,1]
//        int[] arr = {1, 1};

        // [1,1, 1]
        int[] arr = {5, 5, 0};

        int[] ints = test.smallestSubarrays(arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] smallestSubarrays(int[] nums) {
        int length = nums.length;
        int[] arr = new int[length];
        arr[length - 1] = nums[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            arr[i] = nums[i] | arr[i + 1];
        }
        int[] values = new int[length];
        int[] counts = new int[32];
        int j = 0;
        for (int i = 0; i < length; i++) {
            int m = arr[i];
            if (i != 0) {
                sub(counts, nums[i - 1]);
            }
            while (j < length) {
                if (getInt(counts) == m) {
                    j = Math.max(j, i + 1);
                    break;
                }
                add(counts, nums[j++]);
            }
            values[i] = j - i;
        }
        return values;
    }

    private void add(int[] counts, int v) {
        int t = 1;
        for (int i = 0; i < 32; i++) {
            if ((v | t) == v) {
                counts[i]++;
            }
            t <<= 1;
        }
    }

    private void sub(int[] counts, int v) {
        int t = 1;
        for (int i = 0; i < 32; i++) {
            if ((v | t) == v) {
                counts[i]--;
            }
            t <<= 1;
        }
    }

    private int getInt(int[] counts) {
        int item = 0;
        for (int i = 0; i < 32; i++) {
            if (counts[i] > 0) {
                item += (1 << i);
            }
        }
        return item;
    }

}
